回文自动机(PAM)

一.概念

1.回文自动机

回文自动机,又叫回文树,是一种能在Θ(n)\Theta(n)时间玄学解决回文串问题的一种结构,代码难度也十分和蔼可亲。

回文树上的每个节点都代表一个不同的回文子串,相同的回文子串在同一节点。

值得注意的是,回文树上有两个根,0根以及-1根,分别表示空串和-1串,其本质是考虑奇串和偶串。

回文树上有两种边,一种是转移边,另一种是后缀边。

2.转移边

若回文串 SS 有一条 chch 的转移边到 SS' ,说明存在一个回文串 SS 两端各增加1个字符 chch ,将形成回文串 SS'

特殊的,对于 1-1 根的转移边,表示单个字符表示的回文串,如 aa

3.后缀边

若回文串 SS 有一条后缀边连接到 SS' ,说明 SS'SS最大回文串后缀(不含SS 自身)。

对于 00 根和 1-1 根,其后缀边都连向 1-1 根,为的是统一奇串和偶串。

因为每个节点只会向上有一条后缀边,所以所有后缀边会形成一棵树。

4.例子

黑色的边为转移边,红色的边为后缀边。

如图,5号节点代表的回文串为 babbab , 9号节点代表的回文串为 caaccaac

二.构造

和后缀自动机一样,回文自动机使用增量法构造。在构造之前,定义一些变量:

Trans[u][ch]Trans[u][ch] , 点 uu 前后各增加一个字符 chch 得到的点。

Link[u]Link[u] , 点 uu 的后缀边指向的点。

Len[u]Len[u] , 点 uu 所表示的回文串的长度。特殊的,为了得到奇串1-1 根的 LenLen1-1

str[i]str[i] 表示需要构造的串的第 ii 位。

LastLast , str[i1]str[i-1] 为右端点的最长回文子串的标号(必定存在,因为可以单独一个字符作为回文串)。


str[ilen[Last]1]str[i]str[i-len[Last]-1]≠str[i] ,即 i1i-1 的最长回文串无法通过前后拓展一个字符 S[i]S[i] 形成更长的回文串。

那么我们将 LastLast 设为 Link[Last]Link[Last] ,寻找它的最长回文后缀,最终一定能找到。最坏情况下来到 1-1 根 , 此时一定满足条件。将现在到达的点记为 uu

找到后,说明 uu 可以前后加上 str[i]str[i] 形成一个更长的回文串,那么str[i]str[i]为右端点的最长回文串就找到了。

  1. 若此时 Trans[u][str[i]]Trans[u][str[i]] 不等于 00 ,也就是已经有一个这样的回文串了,那么将 LastLast 设置为 Trans[u][str[i]]Trans[u][str[i]] , 结束。

  2. 若不存在这样的回文串,需要新建一个节点 NewnodeNewnode 表示这个回文串。将 Trans[u][str[i]]Trans[u][str[i]] 设为 NewnodeNewnode ,并将 len[Newnode]len[Newnode] 设为 len[u]+2len[u]+2 。顺着 uuLinkLink 链走,直到再次出现 str[ilen[u]1]=str[i]str[i-len[u]-1]=str[i] 的位置, 此时将 link[Newnode]link[Newnode] 连向 Trans[u][str[i]]Trans[u][str[i]] 即可。

图解过程可以看看这篇博客

三.复杂度

1.空间复杂度

空间复杂度是 Θ(nk)\Theta(nk)nn是字符串长度 , kk 是字符集大小。

不过可以通过Map\text{Map}优化空间。

2.时间复杂度

并不会证明,大概是建立后缀边的时候,一旦走过了一个点,之后再在后缀链上走时将会跳过该点。也就是复杂度均摊 Θ(n)\Theta(n)

五.例题

先附一份模板:

struct Palindromes_Automaton {
    int Size , Last , Root0 , Root1 , Trans[ MAXN + 5 ][ MAXK + 5 ] , Link[ MAXN + 5 ];
    int Len[ MAXN + 5 ];

    Palindromes_Automaton( ) {
        Root0 = Size ++ , Root1 = Size ++; Last = Root1;
        Len[ Root0 ] = 0  , Link[ Root0 ] = Root1;
        Len[ Root1 ] = -1 , Link[ Root1 ] = Root1; 
    }

    void Extend( int ch , int dex ) {
        int u = Last;
        for( ; str[ dex ] != str[ dex - Len[ u ] - 1 ] ; u = Link[ u ] );
        if( !Trans[ u ][ ch ] ) {
            int Newnode = ++ Size , v = Link[ u ];
            Len[ Newnode ] = Len[ u ] + 2;
            for( ; str[ dex ] != str[ dex - Len[ v ] - 1 ] ; v = Link[ v ] );
            Link[ Newnode ] = Trans[ v ][ ch ]; Trans[ u ][ ch ] = Newnode;
        }
        Last = Trans[ u ][ ch ];
    }
    void Build( char *str ) {
        int len = strlen( str );
        for( int i = 0 ; i < len ; i ++ )
            Extend( str[ i ] - 'a' + 1 , i );
    }
}PAM;

int main() {
    scanf("%s", str );
    PAM.Build( str );
    printf("%lld", PAM.Calc( ) );
    return 0;
}

1.P5496 【模板】回文自动机(PAM)

题解

2.SP7586 NUMOFPAL - Number of Palindromes

题解

3.P3649 [APIO2014]回文串

题解

4.P4555 [国家集训队]最长双回文串

题解

5.CF17E Palisection

题解